// 两个0和1数量相等区间的最大长度
// 给出一个长度为n的01串，现在请你找到两个区间
// 使得这两个区间中，1的个数相等，0的个数也相等
// 这两个区间可以相交，但是不可以完全重叠，即两个区间的左右端点不可以完全一样
// 现在请你找到两个最长的区间，满足以上要求
// 返回区间最大长度
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

// 暴力方法
// 为了验证
int len1(vector<int>& arr)
{
    unordered_map<int, unordered_map<int, int>> map;
    for(int i = 0; i < arr.size(); ++i)
    {
        int zero = 0, one = 0;
        // 统计 [i, j] 区间内的 0 和 1 的个数
        for(int j = i; j < arr.size(); ++j)
        {
            zero += arr[j] == 0 ? 1 : 0;
            one += arr[j] == 1 ? 1 : 0;
            ++map[zero][one];
        }
    }
    int ans = 0;
    for(auto& [zeros, kv] : map)
    {
        for(auto& [ones, num] : kv)
        {
            // 0 的数量相等，1 的数量也相等的区间多于 1 个
            if(num > 1)
            {
                ans = max(ans, zeros + ones);
            }
        }
    }
    return ans;
}

// 正式方法
// 时间复杂度O(n)
int len2(vector<int>& arr)
{
    int leftZero = -1;
    int rightZero = -1;
    int leftOne = -1;
    int rightOne = -1;
    int n = arr.size();
    for(int i = 0; i < n; ++i)
    {
        if(arr[i] == 0)
        {
            leftZero = i;
            break;
        }
    }
    for(int i = 0; i < n; ++i)
    {
        if(arr[i] == 1)
        {
            leftOne = i;
            break;
        }
    }
    for(int i = n - 1; i >= 0; --i)
    {
        if(arr[i] == 0)
        {
            rightZero = i;
            break;
        }
    }
    for(int i = n - 1; i >= 0; --i)
    {
        if(arr[i] == 1)
        {
            rightOne = i;
            break;
        }
    }
    // 0 ... 0
    // [leftZero + 1, rightOne - 1] 这个区间是两个区间的公共部分，
    // 这两个区间分别加上一个 0，那么这两个区间的 1 的个数相等，0 的
    // 个数也相等
    int p1 = rightZero - leftZero;
    int p2 = rightOne - leftOne;
    return max(p1, p2);
}

// 为了测试
vector<int> randomArray(int len)
{
    vector<int> ans(len);
    for(int i = 0; i < len; ++i) ans[i] = rand() % 2;
    return ans;
}

// 为了测试
int main()
{   
    srand(time(nullptr));
    int N = 500;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 2;
        vector<int> arr = randomArray(n);
        int ans1 = len1(arr);
        int ans2 = len2(arr);
        if(ans1 != ans2) cout << "出错了！" << endl;
        if(i % 100 == 0) cout << "(测试到第" << i << "组)" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}